package com.leetcode.algorithm.y22.m06;

/**
 * 42. 接雨水
 * 
 * https://leetcode.cn/problems/trapping-rain-water/
 * 
 * @author jie.deng
 *
 */
class Question0042Solution01 {

	public int trap(int[] height) {
		// 对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值
		// 下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去height[i]
		int len = height.length;

		// leftArr[i] = height[0...i]中最大数
		int[] leftArr = new int[len];
		leftArr[0] = height[0];
		for (int i = 1; i < height.length; i++) {
			leftArr[i] = Math.max(height[i], leftArr[i - 1]);
		}

		// rightArr[i] = height[i...len-1]中最大数
		int[] rightArr = new int[len];
		rightArr[len - 1] = height[len - 1];
		for (int i = len - 2; i >= 0; i--) {
			rightArr[i] = Math.max(height[i], rightArr[i + 1]);
		}

		int sum = 0;
		for (int i = 0; i < len; i++) {
			int diff = Math.min(leftArr[i], rightArr[i]) - height[i];
			if (diff > 0) {
				sum += diff;
			}
		}
		return sum;
	}

}